package pro.softzhang.algo.lc600;

import pro.softzhang.algo.common.TreeNode;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * root = [8,6,10,5,7,9,11], k = 12
 */
public class LC653_TwoSumIvInputIsABST {
    public static void main(String[] args) {
        TreeNode root = new TreeNode();
        boolean hasTarget = new Solution().findTarget(root, 12);
        System.out.println(hasTarget);
    }

    /**
     *
     */
    static
    class Solution {
        public boolean findTarget(TreeNode root, int k) {
            Set<Integer> set = new HashSet<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode current = root;
            while (current != null || !stack.isEmpty()) {
                while (current != null) {
                    stack.push(current);
                    current = current.left;
                }
                current = stack.pop();
                if(set.contains(k - current.val)) {
                    return true;
                }
                set.add(current.val);
                current = current.right;
            }
            return false;
        }
    }
}
